Halftoning is a technique that is commonly used in digital imaging to create the appearance of intermediate tones when only two colorant levels (i.e., ink or no ink) are available. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that intermediate tone levels can be created by turning some of the pixels “on” and some of the pixels “off” in some small region. The fraction of the pixels which are turned on will determine the apparent gray level. Examples of common halftoning techniques include ordered dither and error-diffusion.
The ordered dither technique is typically implemented by forming a dither matrix having MxxMy elements which is tiled across the image. The elements of the dither matrix are distributed across the range of expected input tone values so that the full range of tones can be reproduced. A basic flow chart for this approach is shown in FIG. 1. A given pixel in the image has column and row addresses x and y, respectively, and an input pixel value I(x,y). Modulo operators 10 are used to determine indices xd and yd that are used to address the dither matrix 12. The threshold value d(xd,yd) stored in the dither matrix at this address is then compared to the input pixel value I(x,y) using a comparator 14. If the input pixel value is equal to or below the threshold value, the output pixel value O(x,y) is set to “off”; if the value is above the threshold, the output pixel value O(x,y) is set to “on”.
A second implementation of this basic technique is shown in FIG. 2. In this case the threshold value d(xd,yd) is combined with the input pixel value I(x,y) using an adder 24. A threshold operator 26 is then used to threshold the combined value to determine the output pixel value O(x,y).
Another implementation of this basic technique is shown in FIG. 3. In this case a set of k dither bitmaps 32 are formed corresponding to the halftone patterns formed when the dither matrix is thresholded at each input level k. The input pixel value I(x,y) is then used to select which of the dither bitmaps should be used for each pixel. Modulo operators 30 are used to determine indices xd and yd that are used to address the selected dither bitmap to determine the output pixel value O(x,y). This implementation has the advantage that fewer computations are necessary to process each pixel. It should be noted that any dither pattern which can be implemented using the methods of FIG. 1 and FIG. 2 can also be implemented using the method of FIG. 3. However, it is possible to define a set of dither bitmaps for the method of FIG. 3 that could not be implemented using the other methods. This is because in the dither matrix implementations once a certain pixel is turned on at the input value corresponding to the threshold, it will stay on for all higher input values. With the dither bitmaps approach this constraint is not present. For example, a certain pixel could be “off” for an input value of 150, “on” for an input value of 151, and “off” again for an input value of 152.
Yet another implementation of this basic technique is shown in FIG. 4. In this case a set of dither look-up tables (LUTs) 36. The dither LUTs 36 are addressed by the input pixel value I(x,y) and store the corresponding output pixel value to be produced at some pixel location. Modulo operators 30 are used to determine indices xd and yd that are used to address a dither LUT selector 34 which selects one of the dither LUTs 36. The output pixel value O(x,y) is determined by addressing the selected dither LUT with the input pixel value I(x,y). This implementation also has the advantage that fewer computations are necessary to process each pixel. It should be noted that any dither pattern which can be implemented using the methods of FIG. 1 and FIG. 2 can also be implemented using the method of FIG. 4. However, as with the method shown in FIG. 3, it is also possible to define a set of dither LUTs 36 that could not be implemented using the other methods.
A variety of different dither matrices have been used in the past which create resulting images with different visual characteristics. Common types include random dither matrices, clustered-dot dither matrices, and Bayer (dispersed dot) dither matrices. U.S. Pat. No. 4,920,501, issued Apr. 24, 1990 to Sullivan et al. discloses a technique to design dither bitmaps which have minimum visual modulation. These patterns are sometimes called “blue-noise” patterns. They are attractive in that the patterns that are produced have minimum visibility to human observers, and as a result the images produced are visually pleasing relative to images produced using other patterns. The basic procedure involved in the creation of these patterns is to use an optimization technique, such as stochastic annealing, to determine the arrangement of the matrix elements which minimizes some cos t function based upon weighting the frequency components of the halftone patterns with a human visual sensitivity function. Sullivan and Ray have also disclosed an enhancement to this method which insures that the bitmaps for each of the gray levels are correlated in such a way that they can be implemented using a dither matrix (see U.S. Pat. No. 5,214,517 issued May 25, 1993 to Sullivan et al.). Other extensions to this basic approach include a method for simultaneously optimizing all of the gray levels (see U.S. Pat. No. 5,754,311 issued May 19, 1998 to Ray), and a method for designing blue-noise dither matrices for use with multi-level output devices (see U.S. Pat. No. 5,586,203, issued Dec. 17, 1996 to Spaulding et al.).
Parker et al. (see U.S. Pat. No. 5,111,310 issued May 5, 1992) and Lin (see U.S. Pat. No. 5,317,418 issued May 31, 1994, and U.S. Pat. No. 5,469,515 issued Nov. 21, 1995) have also recently introduced techniques for the design of dither patterns. Although the actual optimization methods that they have used are somewhat different, the resulting patterns are quite similar to those created using the methods described in the Sullivan et al. patents.
When producing color images on binary output devices, it is necessary to halftone each of the color channels. Typically the color planes are cyan, magenta and yellow (CMY), or cyan, magenta, yellow and black (CMYK). If the same halftoning pattern is used for each of the color channels, this is known as “dot-on-dot” printing. This approach is rarely used in practice because it results in a higher level of luminance modulation, and additionally the color reproduction characteristics will be more sensitive to registration errors. The higher level of luminance modulation will cause the halftone patterns to be more visible than one of the color channels printed alone. The increased sensitivity to registration errors may cause the reproduced color to drift page to page, or even within a page, as the registration characteristics of printing apparatus change. In the graphic arts field the preferred solution has typically been to decorrelate the halftone patterns by rotating the halftone patterns to different “screen angles.” For conventional graphic arts halftone methods, this rotation can either be accomplished optically or digitally.
A number of techniques have been suggested for decorrelating the halftone patterns used for ordered dither (for example see U.S. Pat. No. 5,341,228 issued Aug. 23, 1994 to Parker et al.). These include using independently derived dither matrices for each color channel, spatially shifting the dither matrix patterns for each color plane relative to a reference dither matrix, and using an inverse dither matrix for one or more of the color channels. Each of these techniques has the advantage that the halftone patterns for the different color channels will be decorrelated, and therefore the resulting halftone image should produce lower amounts of luminance modulation and sensitivity to registration errors relative to the nominal dot-on-dot printing case. However, none of these techniques will produce images that exhibit optimal appearance, particularly with respect to the visibility of the halftone patterns.
U.S. Pat. No. 5,822,451 issued Oct. 13, 1998 to Spaulding et al. discloses a method for halftoning a multi-channel digital color image wherein dither matrices for the different color channels of the color image are designed jointly to minimize a visual cos t function. One embodiment of this method is shown in FIG. 5. It can be seen that a conventional dither halftoning method like that shown in FIG. 1 is applied to each channel of a multi-channel color image, wherein the dither matrices used for each color channel are jointly optimized. In particular, a multi-channel input color image having a cyan input image 40A, a magenta input image 40B, and a yellow input image 40C is processed to form a multi-channel output color image having a corresponding cyan output image 48A, magenta output image 48B, and yellow output image 48C. Modulo operators 42A, 42B, and 42C are used to determine the dither matrix column and row addresses xd and yd, respectively for an input pixel having image column and row addresses x and y, respectively. The dither matrix column and row addresses are used to address jointly optimized dither matrices 44A, 44B, and 44C which are jointly optimized for the cyan, magenta and yellow color channels to determine cyan, magenta, and yellow dither values dc(xd,yd), dm(xd,yd), and dy(xd,yd), respectively. The addressed dither values are then compared to the input pixel values, Ic(x,y), Im(x,y), and Iy(x,y) for the corresponding color channels using comparators 46A, 46B, and 46C to determine the output pixel values Oc(x,y), Om(x,y), and Oy(x,y). If the input pixel value is larger than the addressed dither value, the comparator will turn the output pixel value to “on.” Conversely, if the input pixel value is equal to or smaller than the addressed dither value, the comparator will turn the output pixel value to “off.” Any other variety of dither algorithms could also be used, such as the methods shown in FIG. 2, FIG. 3 or FIG. 4.
While the method of Spaulding et al. produces excellent results for conventional CMY(K) printers, some recently introduced printers include multiple colorants having different density levels for one or more of the printer's color channels. For example, these printers may use both a light cyan ink and a dark cyan ink. Likewise there may also be similar light/dark ink pairs for the black, magenta and/or yellow channels.
When light/dark ink pairs are used, there are many ways to determine the color values for each of the color channels. For example, the color values for the light/dark color channels may be determined by splitting a corresponding input color channel. For example, a cyan input color channel can be split into a light cyan color channel and a dark cyan color channel by using the cyan color value to address a look-up table for the light cyan color channel, and a second look-up table for the dark cyan color channel as taught by Couwenhoven et al in U.S. patent application Ser. No. 09/455,981, filed Dec. 6, 1999. Alternatively, the color values for the light/dark color channels can be determined using more complicated color modeling techniques. In that case, a multi-dimensional look-up table, or some other complex function may be necessary to compute the color values.
While the halftoning method of Spaulding et al. taught in U.S. Pat. No. 5,822,451 cited above, can, in general, be applied to determine dither matrices for a set of color channels, including the light and dark ink color channels, there are several limitations to this approach. First of all, the computational complexity of the optimization process increases substantially with every additional color channel, which can make determination of the dither matrices impractical in some cases. Secondly, the definition of the visual cos t function values can become quite ambiguous due to the complex relationship that may exist between the amounts of the individual colorants that are used in different parts of color space. Additionally, it is desirable, in many cases, to minimize the overlap of the light/dark ink pairs in order to minimize the amount of white paper that results when there is partial coverage in the light/dark color channels. The prior art makes no provision for meeting this criterion while maintaining the desirable characteristics of the jointly optimized dither patterns. For example, if a given color calls for 50% coverage of light cyan ink and 50% coverage of dark cyan ink, the method of Spaulding et al may produce dither patterns where some pixels have neither light ink or dark ink, and other pixels have both light ink and dark ink.
There is a need therefore for an improved method for halftoning a multi-channel digital color image having similar color channels that avoids the problems noted above.